package LimitedTimeGame.Day_0305;

/**
 * @author zxc
 * @date 2023/03/05 10:56
 **/

import java.util.*;

/**
 * 题目 ：二叉树中第K大层和
 * 题目详述 ：
 * 给你一棵二叉树的根节点 root 和一个正整数 k 。
 * 树中的 层和 是指 同一层 上节点值的总和。
 * 返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
 * 注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
 *
 * 提示：
 * 树中的节点数为 n
 * 2 <= n <= 105
 * 1 <= Node.val <= 10^6
 * 1 <= k <= n
 *
 */
public class KthLargestLevelSum {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        List<Long> list = new ArrayList<>();
        stack1.push(root);
        long number = 0;
        while(!stack1.isEmpty()){
            TreeNode popNode = stack1.pop();
            number += popNode.val;
            if(popNode.left != null){
                stack2.push(popNode.left);
            }
            if(popNode.right != null){
                stack2.push(popNode.right);
            }
            if(stack1.isEmpty()){
                list.add(number);
                number = 0;
                stack1 = stack2;
                stack2 = new Stack<>();
            }
        }
        int len = list.size();
        long[] dp = new long[len];
        int n = 0;
        for (Long value : list) {
            dp[n++] = value;
        }
        Arrays.sort(dp);
        if(len > k){
            return dp[len - k];
        }
        return -1;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
      }
    }
}
